package h0808;

import java.util.Arrays;
/**
  * @description  leetcode 698. 划分为k个相等的子集
  * @author 不知名帅哥
  * @date 2024/8/8 12:42
  * @version 1.0
*/
public class PartitionKSubsets {
    public static void main(String[] args) {
        int[] nums1 = {4, 3, 2, 3, 5, 2, 1};
        int k1 = 4;
        System.out.println(canPartitionKSubsets(nums1, k1)); // 输出: true

        int[] nums2 = {1, 2, 3, 4};
        int k2 = 3;
        System.out.println(canPartitionKSubsets(nums2, k2)); // 输出: false
    }

    public static boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) {
            return false;
        }
        int target = sum / k;
        Arrays.sort(nums);
        int n = nums.length;
        if (nums[n - 1] > target) {
            return false;
        }
        boolean[] visited = new boolean[n];
        return canPartition(nums, visited, 0, k, 0, target);
    }

    private static boolean canPartition(int[] nums, boolean[] visited, int startIndex, int k, int currentSum, int target) {
        if (k == 1) {
            return true;
        }
        if (currentSum == target) {
            return canPartition(nums, visited, 0, k - 1, 0, target);
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (!visited[i] && currentSum + nums[i] <= target) {
                visited[i] = true;
                if (canPartition(nums, visited, i + 1, k, currentSum + nums[i], target)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        return false;
    }
}
